package offer;

/**
 * @author ZhanBo
 * @date 2020/5/27
 */
public class Solution54 {

    int result =0;
    int k= 0;

    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        descendingOrder(root);
        return result;
    }

    /**
     * 给定一棵二叉搜索树，请找出其中第k大的节点。
     *
     * 输入: root = [3,1,4,null,2], k = 1
     * 输出: 4
     *
     *  root = [5,3,6,2,4,null,null,1], k = 3
     *  输出: 4
     * @param root
     * @return
     */
    public void descendingOrder(TreeNode root) {
        //右递归走路已经到最大的结点
        if (root.right!=null){
            descendingOrder(root.right);
        }
        //已经找到
        if (k == 0) {
            return;
        }
        //找到
        if (--k == 0){
            this.result = root.val;
        }
        if (root.left!=null){
            descendingOrder(root.left);
        }
    }
}
